/*
 * RegionBoard.cpp
 *
 *  Created on: Jun 3, 2011
 *      Author: hongyang
 */

#include "RegionBoard.h"
#include "../smartgame/SgArrayList.h"
#include "../smartgame/SgConnCompIterator.h"

namespace {
static const bool DEBUG_REGION_BOARD = false;
}

RegionBoard::RegionBoard(Board& board) :
	board(board) {
}

RegionBoard::~RegionBoard() {
	clear();
}

void RegionBoard::clear() {
	allRegions[SG_BLACK].Clear();
	allRegions[SG_WHITE].Clear();
	for (int i = 0; i < SG_MAXPOINT; i++)
		regions[SG_BLACK][i] = 0;
	for (int i = 0; i < SG_MAXPOINT; i++)
		regions[SG_WHITE][i] = 0;
}

void RegionBoard::copy(const RegionBoard& b) {
	if (DEBUG_REGION_BOARD)
		SgDebug() << "copy rb\n";
	clear();
	for (SgVectorIteratorOf<Region> sit(b.allRegions[SG_BLACK]); sit; ++sit) {
		Region* old = *sit;
		Region* gen = genRegion(old->getColor());//new Region(*old);
		for (SgVectorIteratorOf<Block> sit(old->getBlocks()); sit; ++sit) {
			Block* bOld = *sit;
			Block* bGen = board.anchor(bOld->getAnchor());
			if (bGen != 0) {
				//bGen->print();
				gen->addBlock(bGen);
			}
		}
		if (gen->numBlocks() == 0)
			removeRegion(gen);
		else
			setRegionArrays(gen);
	}
	for (SgVectorIteratorOf<Region> sit(b.allRegions[SG_WHITE]); sit; ++sit) {
		Region* old = *sit;
		Region* gen = genRegion(old->getColor());//new Region(*old);
		for (SgVectorIteratorOf<Block> sit(old->getBlocks()); sit; ++sit) {
			Block* bOld = *sit;
			Block* bGen = board.anchor(bOld->getAnchor());
			if (bGen != 0) {
				//bGen->print();
				gen->addBlock(bGen);
			}
		}
		if (gen->numBlocks() == 0)
			removeRegion(gen);
		else
			setRegionArrays(gen);
	}
}

Region* RegionBoard::genRegion(SgBlackWhite moveColor) {
	if (DEBUG_REGION_BOARD)
		SgDebug() << "gen region\n";
	Region* r = new Region(board, moveColor);
	addRegion(r);
	return r;
}

void RegionBoard::addRegion(Region* r) {
	//r->findBlocks();
	//r->computeBasicFlags();
	SgBlackWhite color = r->getColor();
	//	if (HEAVYCHECK)
	//		SG_ASSERT(! AllRegions(color).Contains(r));
	allRegions[color].PushBack(r);
}

void RegionBoard::setRegionArrays(Region* r) {
	SgBlackWhite color = r->getColor();
	//SgDebug() << "set regions " << r->getId() << r << "\n";
	for (SgVectorIteratorOf<Block> sit(r->getBlocks()); sit; ++sit) {
		for (SgSetIterator reg((*sit)->pointSet()); reg; ++reg) {
			regions[color][*reg] = r;
			//				SgDebug() << SgWritePoint(*reg) << " ";
		}
	}
	//SgDebug() << "\n";
}

void RegionBoard::onExecMove(Move move) {
	SgPoint p = move.Point();
	SgBlackWhite color = move.Color();
	if (DEBUG_REGION_BOARD)
		SgDebug() << "OnExecMove " << SgWritePoint(p) << '\n';

	if (p != SG_PASS && !board.lastMoveInfo(GO_MOVEFLAG_ILLEGAL)) {

		updateRegion(move);
		// what is this??
		// if the region is split by this move
		SgVectorOf<Region> regions;
		SgPointSet set;
		set.Include(p);
		set |= set.Border(SG_MAX_SIZE);
		regionsAt(set, SgOppBW(color), regions);
		if (regions.Length() > 1)
			if (DEBUG_REGION_BOARD)
				SgDebug() << "warn " << "more than one??\n";
		if (regions.Length() == 0)
			if (DEBUG_REGION_BOARD)
				SgDebug() << "info " << "no neighbors found\n";
		//print(regions);
		for (SgVectorIteratorOf<Region> sit(regions); sit; ++sit) {
			Region* opp = regions[0];//*sit;
			if (opp->isDeleted())
				continue;
			opp->computeStrength();
			bool connected = false;//opp->isConnected();//GoEyeUtil::IsSplitPt(p, opp->area());
			if (!connected && opp->numBlocks() > 1) {
				if (DEBUG_REGION_BOARD)
					SgDebug() << "split\n";
				removeRegion(opp);
				SgVectorOf<Block> blocks = SgVectorOf<Block> (opp->getBlocks());
				while (!blocks.IsEmpty()) {
					Region* r = genRegion(opp->getColor());
					Block* b = blocks.PopFront();
					r->addBlock(b);
					expandRegion(r);
					blocks.Exclude(r->getBlocks());
				}
			}
		}
	}

	if (DEBUG_REGION_BOARD)
		print();
}

void RegionBoard::removeRegion(Region* r) {
	if (DEBUG_REGION_BOARD) {
		SgDebug() << "---------------remove region " << "\n";
		r->print();
	}
	r->setDelete();
	SgBlackWhite color = r->getColor();

	for (SgVectorIteratorOf<Block> sit(r->getBlocks()); sit; ++sit) {
		for (SgSetIterator pit((*sit)->pointSet()); pit; ++pit)
			regions[color][*pit] = 0;
	}

	bool found = allRegions[r->getColor()].Exclude(r);
	SG_UNUSED(found);
	//SG_ASSERT(found);
}

void RegionBoard::regionsAt(const SgPointSet& area, SgBlackWhite color,
		SgVectorOf<Region>& regions) const {
	for (SgVectorIteratorOf<Region> it(getAllRegions(color)); it; ++it) {
		Region* r = *it;
		SgPointSet boundary = r->boundary(true);
		SgPointSet set = boundary.Border8(SG_MAX_SIZE);
		if (set.Overlaps(area) || set.Overlaps(boundary)) {
			//SgDebug() << "find region " << SgWritePointSet(set) << "\n";
			regions.PushBack(*it);
		}
	}
}

/**
 * 1. if the move expands a previous block,
 * 2. if it connects several blocks,
 * 3. if it is a single block.
 */
void RegionBoard::updateRegion(Move move) {
	if (DEBUG_REGION_BOARD)
		SgDebug() << "--------------------------update region " << "\n";
	SgPoint p = move.Point();
	Block* b = board.anchor(p);

	Region* r;// = prevRegionAt(b);

	if (board.lastMoveInfo(GO_MOVEFLAG_CAPTURING)) {
		if (DEBUG_REGION_BOARD)
			SgDebug() << "remove\n";
		removeBlocks(board.getKilled());
	}
	if (board.lastMoveSingle()) {
		r = genRegion(move.Color());
		r->addBlock(b);
	} else {
		//b->print();
		SG_ASSERT(b->numPoints() > 1);
		SgPoint anchor1 = b->getOldPt();
		SgPoint anchor2 = b->getAnchor();
		//SgDebug() << "\nprev reg at " << SgWritePoint(anchor) << "\n";
		r = prevRegionAt(anchor1, anchor2, move.Color());
		if (board.lastMoveMerge()) {
			SgArrayList<Block*, 4> merged = board.getMerged();
			for (SgArrayList<Block*, 4>::Iterator sit(merged); sit; ++sit) {
				//(*sit)->print();
				//SgDebug() << "remove block " << *sit << "\n";
				//SgPointSet area = r->area();
				if (r->containsBlock(*sit))//(*sit)->pointSet().SubsetOf(area))
					r->removeBlock(*sit);
			}
			r->addBlock(b);
		}
	}
	expandRegion(r);
}

void RegionBoard::removeBlocks(SgArrayList<Block*, 4> blocks) {
	SgBlackWhite c = board.toPlay();
	SgVectorOf<Region> removed;
	for (int i = 0; i < blocks.Length(); i++) {
		Block* k = blocks[i];
		SG_ASSERT(k->color() == c);
		for (SgVectorIteratorOf<Region> sit(allRegions[c]); sit; ++sit) {
			Region* r = *sit;
			if (r->containsBlock(k))
				r->removeBlock(k);
			if (r->numBlocks() == 0)
				removed.Include(r);
		}
	}
	for (SgVectorIteratorOf<Region> sit(removed); sit; ++sit)
		removeRegion(*sit);
}

void RegionBoard::expandRegion(Region* r) {
	if (DEBUG_REGION_BOARD)
		SgDebug() << "--------------------expand region\n";
	//r->print();
	SG_ASSERT(r != 0);
	SgBlackWhite c = r->getColor();
	SgPointSet area = r->boundary(false);
	// link it to neighbor regions
	//SgDebug() << "region " << SgWritePointSet(area) << "\n";
	SgVectorOf<Region> regions;
	regionsAt(area, c, regions);
	if (DEBUG_REGION_BOARD) {
		SgDebug() << "regions at \n";
		r->print();
		print(regions);
	}
	// link to neighboring regions;
	Region* current = r;
	for (SgVectorIteratorOf<Region> it(regions); it; ++it) {
		Region* tmp = *it;
		if (tmp == r || tmp->isDeleted())
			continue;
		SG_ASSERT(tmp->getId() != r->getId());
		SgPointSet set = tmp->boundary(false);

		if (simpleCanMerge(area, set, c)) {
			current = mergeRegion(current, tmp);
			area = current->boundary(false);
		}
	}
	if (DEBUG_REGION_BOARD) {
		SgDebug() << "--------------------expand region done\n";
		current->print();
	}
	setRegionArrays(current);
}

Region* RegionBoard::mergeRegion(Region* r1, Region* r2) {
	if (DEBUG_REGION_BOARD)
		SgDebug() << "-----merge region " << r1->getId() << " " << r2->getId()
				<< "\n";
	SgPointSet area;
	//area |= r1->getPoints();
	//area |= r2->getPoints();
	Region* r = genRegion(r1->getColor());
	for (SgVectorIteratorOf<Block> sit(r1->getBlocks()); sit; ++sit)
		r->addBlock(*sit);
	for (SgVectorIteratorOf<Block> sit(r2->getBlocks()); sit; ++sit)
		r->addBlock(*sit);
	removeRegion(r1);
	removeRegion(r2);
	return r;
}

bool RegionBoard::simpleCanMerge(SgPointSet& set1, SgPointSet& set2,
		SgBlackWhite color) const {
	SgBlackWhite opp = SgOppBW(color);
	SgPointSet overlap = set1 & set2;
	//SgDebug() << "overlap " << SgWritePointSet(overlap) << "\n";
	int numOp = board.containsColor(overlap, opp);
	int numSelf = board.containsColor(overlap, color);
	int numEp = board.containsColor(overlap, SG_EMPTY);
	if (numSelf * 2 + numEp - numOp * 2 > 1)
		return true;
	if (numSelf + numEp >= 2)
		return true;
	if (numSelf + numEp == 1 && board.numNeigh(overlap[0], opp) == 0)
		return true;
	SgPointSet expand = set1.Border(SG_MAX_SIZE);
	SgPointSet backup;
	int count = 0;
	//SgDebug() << "check can merge\n";
	//SgDebug() << SgWritePointSet(expand) << " and " << SgWritePointSet(set2);
	for (SgSetIterator sit(expand); sit; ++sit) {
		SgPoint p = *sit;
		if (set2.Contains(p)) {
			if (board.isEmpty(p) && board.numNeigh(p, opp) == 0)
				count++;
			if (!board.isEmpty(p) && board.getColor(p) == color)
				count++;
		}
		if (count >= 2)
			return true;
	}
	return false;
}

void RegionBoard::print() const {
	SgDebug() << SgBW(SG_BLACK) << " regions\n";
	for (SgVectorIteratorOf<Region> sit(allRegions[SG_BLACK]); sit; ++sit)
		(*sit)->print();
	SgDebug() << SgBW(SG_WHITE) << " regions\n";
	for (SgVectorIteratorOf<Region> sit(allRegions[SG_WHITE]); sit; ++sit)
		(*sit)->print();
}

void RegionBoard::print(const SgVectorOf<Region> regions) const {
	for (SgVectorIteratorOf<Region> sit(regions); sit; ++sit)
		(*sit)->print();
}

/*
 void RegionBoard::endOfGame(SgBlackWhite player) const {
 for (SgVectorIteratorOf<Region> sit(allRegions[player]); sit; ++sit) {

 }
 }
 */

SgBlackWhite RegionBoard::whoWins() const {
	float black = board.stonesKilled(SG_WHITE) * 2;
	float white = board.stonesKilled(SG_WHITE) * 2;

	for (SgVectorIteratorOf<Region> rit(allRegions[SG_BLACK]); rit; ++rit) {
		Region* r = *rit;
		if (r->isAlive())
			black += r->numPoints();
		else {
			for (SgVectorIteratorOf<Block> sit(r->getBlocks()); sit; ++sit)
				board.killBlock(*sit);
			white += r->numPoints() * 2;
		}
	}

	for (SgVectorIteratorOf<Region> rit(allRegions[SG_WHITE]); rit; ++rit) {
		Region* r = *rit;
		if (r->isAlive())
			white += r->numPoints();
		else
			black += r->numPoints() * 2;
	}

	float res = black - white - board.komi() + board.estimateEmptyPts();
	if (res >= 0.0)
		return SG_BLACK;
	else
		return SG_WHITE;
}

bool RegionBoard::isWrapped(Region& r) const {
	//if(DEBUG_REGION_BOARD)
	//	SgDebug() << "is wrapped begin\n";
	int sW, sE, sS, sN;
	SgPoint p1, p2;
	sW = sE = sS = sN = 0;
	SgPointSet points = r.area();
	//SgPointSet boundary =
	for (SgSetIterator p(points); p; ++p) {
		p1 = p + SG_NS;
		p2 = p1 + SG_NS;
		sN += (SgPointUtil::InBoardRange(p1) && board.getColor(p1) == SG_EMPTY
				&& (!SgPointUtil::InBoardRange(p2) || board.getColor(p2)
						== SG_EMPTY));
		p1 = p - SG_NS;
		p2 = p1 - SG_NS;
		sS += (SgPointUtil::InBoardRange(p1) && board.getColor(p1) == SG_EMPTY
				&& (!SgPointUtil::InBoardRange(p2) || board.getColor(p2)
						== SG_EMPTY));
		p1 = p + SG_WE;
		p2 = p1 + SG_WE;
		sW += (SgPointUtil::InBoardRange(p1) && board.getColor(p1) == SG_EMPTY
				&& (!SgPointUtil::InBoardRange(p2) || board.getColor(p2)
						== SG_EMPTY));
		p1 = p - SG_WE;
		p2 = p1 - SG_WE;
		sE += (SgPointUtil::InBoardRange(p1) && board.getColor(p1) == SG_EMPTY
				&& (!SgPointUtil::InBoardRange(p2) || board.getColor(p2)
						== SG_EMPTY));
	}

	//if(DEBUG_REGION_BOARD)
	//	SgDebug() << "is wrapped end\n";

	return (sN > 1 || sS > 1 || sW > 1 || sE > 1);
}

bool RegionBoard::isDead(Region& r) const {
//	GoEyeCount eye = r.getEyeCount();
	SgPointSet points = r.area();
//	SgDebug()<<"eyes   "<<SgBlackWhite(r.getColor())<<"     ";
//	for (SgSetIterator p(points); p; ++p)
//		SgDebug()<<SgWritePoint(*p)<<"  ";
//	SgDebug()<<eye.MaxEyes()<<"  "<<eye.MaxPotEyes()<<"\n";
//	if (eye.MaxEyes() >= 2)
//		return false;
//	if (eye.MaxPotEyes() >= 2)
//		return false;
//	if (r.enoughEyes())
//		return false;
	if (!isWrapped(r))
		return false;
	SgBlackWhite color = r.getColor();
	if (color == SG_WHITE)
		color = SG_BLACK;
	else
		color = SG_WHITE;
	//SgDebug() << "strength compare begin\n";
	for (SgVectorIteratorOf<Region> it(getAllRegions(color)); it; ++it) {
		Region* r2 = *it;
		bool con = false;
		for (SgSetIterator p2(r2->area()); !con && p2; ++p2)
			for (SgSetIterator p(points); !con && p; ++p) {
				//				SgDebug()<<"distance "<<p<<"  "<<p2<< "begin\n";
				if (SgPointUtil::Distance(*p, *p2) <= 2)
					con = true;
				//				SgDebug()<<"distance "<<p<<"  "<<p2<< "end\n";
			}
		if (con && r.getStrength() >= r2->getStrength()) {
			//SgDebug() << "strength compare end\n";
			return false;
		}
	}
	//SgDebug() << "strength compare end\n";
	return true;
}
